package com.techyuan.algorithm.sorts.select;

import static com.techyuan.algorithm.utils.SortUtils.randomizedPartition;

/**
 * Created by tianjuntao on 2016/12/16.
 */
public class RanomizedSelect implements ISelect {
    public int select(int[] data, int i) {
        return ranomizedSelect(data, 0, data.length - 1, i);
    }

    private int ranomizedSelect(int[] data, int start, int end, int i) {
        if (start == end)
            return data[start];
        int q = randomizedPartition(data, start, end);
        int k = q - start + 1;
        if (i == k)
            return data[q];
        else if (i < k) {
            return ranomizedSelect(data, start, q - 1, i);
        } else
            return ranomizedSelect(data, q + 1, end, i - k);
    }
}
